package src.leetcode.greedy.medium_0053;

public class maxSubArray {

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums.length == 0) return 0;

        int max = nums[0];
        int sum = 0;

        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            if(sum <= 0) sum = 0;
            max = Math.max(max, sum);
        }

        return max;
    }
}
